package acwing;

import java.util.Arrays;
import java.util.Scanner;

/**
 * 1. 问题描述
 *     在一条数轴上有N家商店，他们的坐标分别为A1--AN.
 *     现在需要在数轴上建立一个仓库，每天清晨，从仓库到每家商店需要运送商品
 *     为了提高效率，求把仓库建立在何处，可以使得总路程最小
 *
 * 2. 算法分析
 *      本题是一道典型的中位数模型，实际上建立上述的数学模型非常简单的，问题是如何求解上述的建立的数学模型
 *      假设我们将仓库建立在数轴的x位置，则每家商店到x的距离为abs(A[k] - x),则所有的商店到仓库的距离和：
 *          abs(A[0]-x) + abs(A[1]-x) + ...... + abs(A[N-1]-x)
 *      所以抽象出来的数学模型：
 *          min abs(A[0]-x) + abs(A[1]-x) + ...... + abs(A[N-1]-x)
 *           x
 *      我们需要求出上述的绝对值不等式(凸不等式)
 *
 *
 *     为了简单考虑我们先分析最简答的情况，假设此时只有两个商店，此时我们的不等式为 abs(A[0]-x) + abs(A[1]-x)
 *     显然我们有：
 *          abs(A[0]-x) + abs(A[1]-x) >= abs(A[0]-A[1])
 *     此时只需要x在[A[0],A[1]](假设A[0] < A[1])之间的任意一个位置即可
 *
 *     其次我们考虑三个商店的情况，此时我们将x建立在中间的商店处即可，证明非常简单，由此我们将两种最简单的特殊情况都讨论
 *     清楚了
 *
 *     最后我们考虑最一般的情况，假设此时有N个商店，我们猜测一下两种情况：
 *          N为偶数
 *              此时将仓库建立在中间两个商店之间即可
 *          N为奇数
 *              此时将仓库建立在中间的商店即可
 *
 *     详细证明只需要利用上述的绝对值不等式即可，比较容易
 *
 * 3， 代码实现
 */
@SuppressWarnings("all")
public class Q001_选址问题 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] A = new int[N];
        for(int i = 0; i < N; i++) {
            A[i] = sc.nextInt();
        }
        int res = 0;
        Arrays.sort(A);
        for(int i = 0; i < N / 2; i++) {
            res += A[N-i-1] - A[i];
        }
        System.out.print(res);
    }
}
